#include <stdio.h>
#include <stdlib.h>

#define True 1
#define False 0

char *adj1, *adj2;
int *used, *equiv, V1, V2, E1, E2;

void readin( char **, int *, int *, FILE * ), print_isom( void );
int is_isom( void ), isom( int ), ok_assign( int );
void dump_adj_matrix( char *, int );

void main( int argc, char **argv )
{
   FILE *fp;
   int i;

   if ( ( fp = fopen( argv[ 1 ], "r" ) ) == NULL ) {
      printf( "\nUnable to open file %s for reading\n", argv[ 1 ] );
      exit( EXIT_FAILURE );
   }
   readin( &adj1, &V1, &E1, fp );
   fclose( fp );

   if ( ( fp = fopen( argv[ 2 ], "r" ) ) == NULL ) {
      printf( "\nUnable to open file %s for reading\n", argv[ 2 ] );
      exit( EXIT_FAILURE );
   }
   readin( &adj2, &V2, &E2, fp );
   fclose( fp );

   if ( ( equiv = ( int * ) calloc( V1, sizeof ( int ) ) ) == NULL ) {
      printf( "\nUnable to allocate storage for this size graph\n" );
      exit( EXIT_FAILURE );
   }

   if ( ( used = ( int * ) calloc( V1, sizeof ( int ) ) ) == NULL ) {
      printf( "\nUnable to allocate storage for this size graph\n" );
      exit( EXIT_FAILURE );
   }

   if ( is_isom() ) {
      printf( "\nGraphs are isomorphic\n" );
      print_isom();
   }
   else
      printf( "\nGraphs are not isomorphic\n" );
}

void print_isom( void )
{
   int i;

   printf( "   V1   V2\n" );
   for ( i = 0; i < V1; i++ )
      printf( "%5d%5d\n", i + 1, equiv[ i ] + 1 );
}

void readin( char **adj_ptr, int *v_ptr, int *e_ptr, FILE *fp )
{
   int i, v, w, ignore;

   fscanf( fp, "%d%d", v_ptr, e_ptr );

   if ( ( *adj_ptr = ( char * ) calloc( *v_ptr * *v_ptr, sizeof ( char ) ) )
        == NULL ) {
      printf( "\nUnable to allocate storage for this size graph\n" );
      exit( EXIT_FAILURE );
   }

   for ( i = 0; i < *e_ptr; i++ ) {
      fscanf( fp, "%d%d%d", &v, &w, &ignore );
      (*adj_ptr)[ ( v - 1 ) * *v_ptr + w - 1 ]
         = (*adj_ptr)[ ( w - 1 ) * *v_ptr + v - 1 ] = 1;
   }
}

/* Assume equiv[ 0 ],...,equiv[ k - 1 ] preserves adjacencies and
   k < V1 - 1. Return True if extendable to an isomorphism, and False
   if not. */
int isom( int k )
{
   for ( equiv[ k ] = 0; equiv[ k ] < V1; equiv[ k ]++ ) {
      if ( used[ equiv[ k ] ] )
         continue;
      used[ equiv[ k ] ] = 1;
      if ( ok_assign( k ) )
         if ( k == V1 - 1 || isom( k + 1 ) )
            return True;
      used[ equiv[ k ] ] = 0;
   }

   return False;
}

int is_isom( void )
{
   int i;

   if ( V1 != V2 || E1 != E2 )
      return False;

   return isom( 0 );
}

/* Assume equiv[ 0 ],...,equiv[ k - 1 ] preserves adjacencies.
   Test whether equiv[ 0 ],...,equiv[ k - 1 ],equiv[ k ] preserves
   adjacencies. */
int ok_assign( int k )
{
   int i;

   for ( i = 0; i < k; i++ )
      if ( adj1[ i + k * V1 ] != adj2[ equiv[ i ] + equiv[ k ] * V1 ] )
         return False;

   return True;
}

void dump_adj_matrix( char *a, int n )
{
   int i, j;

   for ( i = 0; i < n; i++ ) {
      for ( j = 0; j < n; j++ )
         printf( "%4d", a[ i * n + j ] );
      putchar( '\n' );
   }
}